[C/C++] 常見排序實作

把常見的排序重新寫過一次，以備不時之需。

程式

#include <iostream>

using namespace std;

void Swap(int &a, int &b){
	int temp = a ;
	a = b ;
	b = temp ;
}

void Bubble_Sort(int *Array, int Size){
	for ( int i = 0 ; i < Size ; i ++ ){
		for ( int j = 0 ; j < Size - 1 ; j ++ ){
			if ( Array[j+1] < Array[j] ){
				Swap(Array[j],Array[j+1]) ;
			}
		}
	}
}

void Select_Sort(int *Array, int Size){
	for ( int i = 0 ; i < Size ; i ++ ){
		int MaxIndex = 0 ;
		for ( int j = 0 ; j < Size - i ; j ++ ){
			if ( Array[MaxIndex] < Array[j] ){
				MaxIndex = j  ;
			}
		}
		Swap(Array[MaxIndex],Array[Size-i-1]) ;
	}
}

void Insert_Sort(int *Array, int Size){
	for ( int i = 1 , j ; i < Size ; i ++ ){
		int temp = Array[i] ;
		for ( j = i - 1 ; j >= 0 && Array[j] > temp ; j -- ){
			Array[j+1] = Array[j] ;
		}
		Array[j+1] = temp ;
	}
}

void Print(int *Array , int Size){
	for ( int i = 0 ; i < Size ; i ++ )
		cout << *(Array+i) << " " ;
}

void Quick_Sort(int *Array, int left , int right){
	if ( right <= left )
		return ;
	int pivot , i , j ;
	pivot = Array[left] ;
	i = left + 1  ;
	j = left + 1;
	while ( i < right ){
		if ( Array[i] <= pivot ){
			Swap(Array[j],Array[i]) ;
			j ++ ;
		}
		i ++ ;
	}
	Swap(Array[left],Array[j-1]) ;
	Quick_Sort(Array,left,j-1) ;
	Quick_Sort(Array,j,right) ;

}

void Merge(int *Array, int left , int mid , int right){
	int *temp = new int[right - left + 1] ;
	int i = left , j = mid + 1 , k = 0 ;
	while( i <= mid && j <= right ){
		if ( Array[i] <= Array[j] ){
			temp[k] = Array[i] ;
			i ++ ;
		} else {
			temp[k] = Array[j] ;
			j ++ ;
		}
		k ++ ;
	}
	while( i <= mid ){
		temp[k] = Array[i] ;
		i ++ ;
		k ++ ;
	}
	while( j <= right ){
		temp[k] = Array[j] ;
		j ++ ;
		k ++ ;
	}
	for ( int i = left , j = 0 ; i <= right ; i ++ , j ++ )
		Array[i] = temp[j] ;
	delete temp ;
}

void Merge_Sort(int *Array , int left ,int right){
	if ( right <= left )
		return ;
	int mid = ( left + right ) / 2 ;
	Merge_Sort(Array,left,mid);
	Merge_Sort(Array,mid+1,right) ;
	Merge(Array,left,mid,right) ;
}

int main()
{
	int Size = 10 ;
	int Array[10] = {10,-5,3,2,7,5,-6,1,2,-3} ;
	//Bubble_Sort(Array,Size) ;
	//Select_Sort(Array,Size) ;
	//Insert_Sort(Array,Size) ;
	//Quick_Sort(Array,0,Size) ;
	//Merge_Sort(Array,0,Size) ;
	Print(Array,Size) ;
	return 0;
}